package com.syq;

public class Sort {
    //===========================冒泡排序算法==========================================
    //https://blog.csdn.net/lu_1079776757/article/details/80459370
    public static void bubbleSort(Integer[] array, int n) {
        int i, j;
        for (i = 0; i < n-1; i++) {//表示 n 次排序过程。
            for (j = 1; j < n - i; j++) {
                if (array[j - 1] > array[j]) {//前面的数字大于后面的数字就交换
                    // 交换 array[j-1]和 array[j]
                    int temp;
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }

    //===========================插入排序算法==========================================
    //https://blog.csdn.net/qq1641530151/article/details/80550296
    public static void insertSort(Integer arr[]) {
        for (int i = 1; i < arr.length; i++) {
            //插入的数
            int insertVal = arr[i];
            //被插入的位置(准备和前一个数比较)
            int index = i - 1;
            //如果插入的数比被插入的数小
            while (index >= 0 && insertVal < arr[index]) {
                //将把 arr[index] 向后移动
                arr[index + 1] = arr[index];
                //让 index 向前移动
                index--;
            }
            //把插入的数放入合适位置
            arr[index + 1] = insertVal;
        }
    }

    //===========================快速排序算法==========================================
    //https://blog.csdn.net/elma_tww/article/details/86164674
    public static void quickSort(Integer[] a, int low, int high) {
        int start = low;
        int end = high;
        int key = a[low];
        while (end > start) {
            //从后往前比较
            while (end > start && a[end] >= key)
                //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                end--;
            if (a[end] <= key) {
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            //从前往后比较
            while (end > start && a[start] <= key) {
                //如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                start++;
                if (a[start] >= key) {
                    int temp = a[start];
                    a[start] = a[end];
                    a[end] = temp;
                }
                //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
            }
            //递归
            if (start > low) quickSort(a, low, start - 1);//左边序列。第一个索引位置到关键值索引-1
            if (end < high) quickSort(a, end + 1, high);//右边序列。从关键值索引+1 到最后一个
        }
    }
}

